package likou.jindian;

public class _02_04 {
    public static void main(String[] args) {
        ListNode node = new ListNode(2);
        ListNode head = node;
        node.next = new ListNode(1);
        head = partition(head, 2);
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

    public static ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode depNode = head;
        ListNode yesNode = null;
        ListNode noNode = null;
        ListNode nextNodeHead = null;
        boolean yesP = true, noP = true;
        while (depNode != null) {
            if (depNode.val < x) {
                if (yesP) {
                    yesP = false;
                    yesNode = new ListNode(depNode.val);
                    head = yesNode;
                } else {
                    yesNode.next = new ListNode(depNode.val);
                    yesNode = yesNode.next;
                }
            }
            if (depNode.val >= x) {
                if (noP) {
                    noP = false;
                    noNode =  new ListNode(depNode.val);
                    nextNodeHead = noNode;
                } else {
                    noNode.next = new ListNode(depNode.val);
                    noNode = noNode.next;
                }
            }
            depNode = depNode.next;
        }
        if(!yesP){
            yesNode.next = nextNodeHead;
        }else{
            head = nextNodeHead;
        }
        return head;
    }
}
